package swardToOffer.abstractModeling;

/**
 * @Author ChanZany
 * @Date 2021/5/27 15:16
 * @Version 1.0
 * 面试题63：股票的最大利润
 * 题目：假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖交易该股
 * 票可能获得的利润是多少？例如一只股票在某些时间节点的价格为{9, 11, 8, 5,
 * 7, 12, 16, 14}。如果我们能在价格为5的时候买入并在价格为16时卖出，则能
 * 收获最大的利润11。
 * XX错误解法:双指针(错误,因为无法确定左指针和右指针的移动边界,遇到ABBBA问题就无法求解,比如7,2,6,4,0,7,输出是7-2=5)
 * 由于股票的买卖需要按照先后顺序,我们定义两个指针left<=right,两个指针同时往中间移动直到相遇
 * 在移动过程中,左指针维护其移动窗口的最小值,右指针维护其移动窗口的最大值,最终可以得到最大利润为 profit=Math.max(max-min,0)
 * 解法1:一次遍历
 * 从左往右遍历价格数组.定义f(i)为当卖出价为数组中第i个数字时可能获得的最大利润.也就是说,
 * 如果在扫描到数组中的第i个数字时,只要我们能记住之前i-1个数字中的最小值,就能算出在当前价位卖出可能得到的最大利润.求f(n=len)即可
 * 解法2:动态规划
 * 状态定义:dp[i]代表以price[i]结尾的子数组的最大利润,即前i天的最大利润.
 * 转移方程:由于题目限定 “买卖该股票一次” ，因此前i日最大利润 dp[i] 等于前 i−1 日最大利润 dp[i-1]和第i日卖出的最大利润中的最大值。
 * dp[i] = max(dp[i-1],prices[i]-min(prices[0:i]))
 * 初始状态,dp[1]=0,即首日利润为0
 * 返回值:dp[n],其中n为价格列表长度
 */
public class MaximalProfit {
    public int maxProfit2(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for (int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost); //dp[i] = max(dp[i-1],prices[i]-min(prices[0:i]))
        }
        return profit;
    }

    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;
        int min = prices[0], maxDiff = prices[1] - prices[0];
        for (int i = 2; i < prices.length; i++) {
            min = Math.min(min, prices[i - 1]);
            maxDiff = Math.max(maxDiff, prices[i] - min);
        }
        return Math.max(maxDiff, 0);
    }

    public static void main(String[] args) {
        MaximalProfit Main = new MaximalProfit();
//        int [] prices = {3,2,6,5,0,3};
        int[] prices = {7, 2, 6, 4, 0, 7};
        System.out.println(Main.maxProfit(prices));
    }
}
